﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MyOnlineScheduling
{
    class TaskHeap
    {
        List<PartTask> taskQueue;

        public TaskHeap()
        {
            taskQueue = new List<PartTask>();
        }

        public int Count()
        {
            return taskQueue.Count;
        }

        public void insert(PartTask newTask)
        {
            taskQueue.Insert(0, newTask);
            heapify(0);
        }

        public void heapify(int i)
        {
            if (i >= taskQueue.Count) return;

            int l = left(i);
            int r = right(i);
            int smallest = i;
            double weightedTimeRemainingI = (double)taskQueue[i].pendingPartDuration / (double)taskQueue[i].weight;
            double weightedTimeRemainingSmallest = weightedTimeRemainingI;

            double weightedTimeRemainingL;
            double weightedTimeRemainingR;

            if (l < taskQueue.Count)
            {
                weightedTimeRemainingL = (double)taskQueue[l].pendingPartDuration / (double)taskQueue[l].weight;
                if (weightedTimeRemainingL < weightedTimeRemainingI)
                {
                    smallest = l;
                    weightedTimeRemainingSmallest = weightedTimeRemainingL;
                }
            }

            if (r < taskQueue.Count)
            {
                weightedTimeRemainingR = (double)taskQueue[r].pendingPartDuration / (double)taskQueue[r].weight;
                if (weightedTimeRemainingR < weightedTimeRemainingSmallest)
                    smallest = r;
            }

            if (smallest != i)
            {
                swap(i, smallest);
                heapify(smallest);
            }
        }

        public PartTask heapGetMin()
        {
            if (taskQueue.Count == 0) return null;

            PartTask min = taskQueue.ElementAt<PartTask>(0);            
            return min;
        }

        public void heapRemoveMin()
        {
            if (taskQueue.Count == 0) return;

            if (taskQueue.Count != 1) swap(0, taskQueue.Count - 1);
            taskQueue.RemoveAt(taskQueue.Count - 1);
            heapify(0);
        }

        public PartTask heapExtractMin()
        {
            if (taskQueue.Count == 0) return null;

            PartTask min = new PartTask(taskQueue.ElementAt<PartTask>(0));
            if (taskQueue.Count != 1) swap(0, taskQueue.Count - 1);
            taskQueue.RemoveAt(taskQueue.Count - 1);
            heapify(0);

            return min;
        }

        private int left(int i)
        {
            return (2 * (i + 1) - 1);
        }

        private int right(int i)
        {
            return (2 * (i + 1));
        }

        private int parent(int i)
        {
            return ((i - 1) / 2);
        }

        private void swap(int first, int second)
        {
            PartTask temp = taskQueue[first];
            taskQueue[first] = taskQueue[second];
            taskQueue[second] = temp;
        }
    }
}
